package com.mamingchao.basic.swardToOffer.two;
/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * 示例:
 *
 * 现有矩阵 matrix 如下：
 *
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 * 给定 target = 5，返回 true。
 * 给定 target = 20，返回 false。
 *
 */
public class FindNumberIn2DArray {
    /**
     * 从右上角开始搜索的解法
     * 时间复杂度：O(n+m)，其中n是行数，m是列数
     * 空间复杂度：O(1)
     */
    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 从右上角开始搜索
        int row = 0;
        int col = cols - 1;

        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                // 如果当前值大于目标值，向左移动一列
                col--;
            } else {
                // 如果当前值小于目标值，向下移动一行
                row++;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        // 测试用例
        int[][] matrix = {
                {1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };

        // 测试用例1：目标值存在
        int target1 = 5;
        boolean result1 = findNumberIn2DArray(matrix, target1);
        System.out.println("测试用例1 - 查找数字 " + target1 + "，预期结果：true，实际结果：" + result1);

        // 测试用例2：目标值不存在
        int target2 = 20;
        boolean result2 = findNumberIn2DArray(matrix, target2);
        System.out.println("测试用例2 - 查找数字 " + target2 + "，预期结果：false，实际结果：" + result2);

        // 测试用例3：空矩阵
        int[][] emptyMatrix = {};
        boolean result3 = findNumberIn2DArray(emptyMatrix, 5);
        System.out.println("测试用例3 - 空矩阵查找，预期结果：false，实际结果：" + result3);

        // 测试用例4：查找最小值
        int target4 = 1;
        boolean result4 = findNumberIn2DArray(matrix, target4);
        System.out.println("测试用例4 - 查找最小值 " + target4 + "，预期结果：true，实际结果：" + result4);

        // 测试用例5：查找最大值
        int target5 = 30;
        boolean result5 = findNumberIn2DArray(matrix, target5);
        System.out.println("测试用例5 - 查找最大值 " + target5 + "，预期结果：true，实际结果：" + result5);
    }
}
